/*
 * @lc app=leetcode.cn id=2 lang=cpp
 *
 * [2] 两数相加
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
using namespace std;

// struct ListNode {
//     int val;
//     ListNode* next;
//     ListNode() : val(0), next(nullptr) {}
//     ListNode(int x) : val(x), next(nullptr) {}
//     ListNode(int x, ListNode* next) : val(x), next(next) {}
// };

class Solution {
   public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* node1 = l1;
        ListNode* node2 = l2;
        ListNode* result = nullptr;  // 保存第一个节点
        ListNode* last = nullptr;    // 保存上一个节点
        int sum = 0, carry = 0;

        while (node1 != nullptr || node2 != nullptr) {
            // 计算当前节点的和，判断是否需要进位
            int num1 = (node1 == nullptr) ? 0 : node1->val;
            int num2 = (node2 == nullptr) ? 0 : node2->val;
            sum = num1 + num2 + carry;
            carry = sum / 10;
            sum = sum % 10;

            // 建立新节点并插入 result
            if (result == nullptr) {
                result = new ListNode(sum);
                last = result;
            } else {
                last->next = new ListNode(sum);
                last = last->next;
            }

            // 切换到下一节点
            node1 = (node1 == nullptr) ? nullptr : node1->next;
            node2 = (node2 == nullptr) ? nullptr : node2->next;
        }

        // 若最高位存在进位
        if (carry == 1) {
            last->next = new ListNode(carry);
        }

        return result;
    }
};
// @lc code=end
